A node is considered in a packet-based communication network. In the node all incoming packets with the same next-hop destination must be transmitted over a single output line towards the next node. Because of the limited bandwidth, an output queue is necessary to resolve contention at the output link. Current networks convey very diverse and heterogeneous traffic and should therefore be able to differentiate the Quality of Service (QoS) according to the specific needs of the individual traffic streams, i.e. deliver a better service for those applications that need it, in exchange for a worse service for other applications. This means the network nodes must be QoS-aware systems that treat packets differently depending on the application they belong to. In the DiffServ framework for IP (Internet Protocol) networks, traffic streams are aggregated into a limited number M of traffic classes (TC), based on the DSCP (Differentiated Services Code Point) field in the IP header, and the handling of packets depends on the traffic class they belong to. Many QoS-aware algorithms exist, both at the application level (e.g. traffic shaping, congestion notification) and at the level of the network (e.g. congestion avoidance, active queue management, specific packet discarding and packet scheduling mechanisms). In the present invention the focus is on the latter, i.e. the scheduling algorithm for the packets in the queues of the output links.
A router's scheduling algorithm is responsible for determining which available packet is the next to be transmitted to the output link. The key technical challenge is to schedule packets in such a way that the joint QoS requirements of the different traffic classes are met as closely as possible, given a certain limited output bandwidth. Targeted QoS criteria usually are per-class output bandwidth, mean packet delay, delay jitter and packet loss probability. QoS provisioning further entails the amount of isolation, fairness, policing and the degree in which these service levels can be guaranteed and enforced.
There exists no single algorithm that can guarantee an ideal distribution of resources in all possible circumstances and under all output bandwidth constraints. Any measure taken to enhance a QoS criterion for one class necessarily degrades the performance of other classes to some extent. This allows for a fair amount of QoS tailoring: performance with regard to a high-utility criterion can be improved at the cost of a worse performance for low-utility criteria. Therefore, scheduling is always a matter of aiming for an agreeable trade-off in satisfying the targeted QoS requirements of the different traffic classes. Seen in this way, any particular scheduling mechanism implements only a subset of the possible ways in which multi-class scheduling can be done, thus covering only part of the possible trade-off choices that can be made. Some of them focus particularly on minimising delay, some on proportionally sharing the output bandwidth, some on meeting strict deadlines and others specifically on the fairness between classes. Usually, however, a mechanism involves changes in several of these aspects.
Various multi-class scheduling mechanisms for packet-based networks have been proposed in the past and some of them are extensively used in present-day routers. In the realm of class-based scheduling the main classical players are the following.
Absolute priority (AP), which is also known as Head-of-Line (HoL), provides an extreme QoS trade-off in the sense that minimising the delay of class-i packets (i=1, . . . , M) is infinitely more important than the delay of packets of class i+1, . . . , M. A separate queue for each class is used and the scheduler always visits the queue that has the lowest class number and is non-empty. The drawback of AP is that no control over the QoS differentiation is possible and that it is only practical for few classes with clearly distinct service requirements. Additionally, classes with lower priority may experience a dramatically high delay, especially when the partial load of the higher-priority classes is high, an effect known as packet starvation.
Some modifications to soften the rigidity of AP have been proposed. A Probabilistic Priority scheme has been presented that assigns a small probability pi to each class by which the server may service a class-(i+1) packet, even though class-i packets are available. Another idea was to allow packets to promote to a higher-priority class under certain well-specified conditions, or conversely, to degrade to a lower class (priority jumps, see e.g. patent document U.S. Pat. No. 6,765,905 B1). Nevertheless, the resulting per-class delay distributions of these solutions are poorly understood and rules to translate delay targets to working parameters are lacking.
Proportional-rate schedulers (also called fair-queueing schedulers (FQ)) consider it fair to guarantee each traffic class a predefined fraction of the output bandwidth. In other words, FQ-schedulers assign the available output rate proportionally, in line with the Proportional-DiffServ framework for QoS provisioning in IP networks. Implementations always use a separate queue for each traffic class (as does AP) and dequeueing is done by visiting these queues in some periodical manner (or otherwise) such as to guarantee rate-proportionality as much as possible. Weighted Fair Queuing (WFQ) optimally achieves proportionality but is computationally very complex, as it needs to recalculate virtual finish times for all queues each time a packet is either enqueued or dequeued anywhere. Many modifications exist: start-time Fair Queueing, self-clocked Fair Queueing, worst-case Fair Weighted Fair Queueing, frame-based Fair Queueing, Weighted Round-Robin, Deficit Round-Robin (DRR), all of which have their specific advantages.
Deadline-based schedulers require each packet to have a strict deadline by which that packet should have been transmitted at the very latest. The QoS provisioning is considered fair as long as all deadlines can be met. If a packet cannot be transmitted before its deadline, the time it is overdue is defined as its lateness. The Earliest Deadline First (EDF) scheduler always transmits the packet with the nearest deadline and is known to achieve the smallest possible overall lateness. The drawback of such deadline-based schedulers, however, is their need to maintain a priority list of all queued packets, resulting in a high complexity. Some patented deadline-based solutions are found in U.S. Pat. No. 7,626,988 and U.S. Pat. No. 6,247,061. Particularly noteworthy is U.S. Pat. No. 7,626,988, which uses separate queues to represent future time quanta, rather than a priority or a flow. A packet is enqueued in that queue which corresponds to the amount of time left before the packet's deadline. This results in a kind of time/space interaction with a QoS target expressed in terms of said future time quanta. As with previous solutions, the actual per-class delay distribution, or even the per-class lateness, of deadline-based schedulers is hard to control or predict. Hence, delay quantile proportionality is not achieved with deadline-based schedulers.
Some solutions try to combine aspects of the above main solution types in order to exploit their advantages under specific conditions or for specific applications. Schedulers have been proposed that modify DRR (fair queueing) to include priority for delay-critical flows. Likewise, fair queueing has been used whereby flows with low enough actual rate compared to their fair share are given absolute priority.
Also the use of in-queue reservations has been described in the prior art. In the paper “Priority Forcing Scheme: a New Strategy for Getting Better than Best Effort Service in IP-Based Network” (Burakowski et al., Proc. IFIP Workshop on Internet Technologies WITASI 2002, 10-11 Oct. 2002, Wroclaw, pp. 135-150) a Priority Forcing Scheme (PFS) is suggested. This scheduler requires the involved applications to make the reservations by sending reservation packets through the network in advance of data packets which contain the actual data. Only network users (applications) that are aware of the Priority Forcing Scheme used in the network nodes can benefit from it. It is also clear that malicious users can easily flood the network with reservation packets, thereby gaining access to all of the resources at the expense of the other users. With PFS, once a reservation packet is seized by a data packet, no new reservation is made. In “On New Strategy for Prioritising the Selected Flow in Queuing System” (Burakowski W. et al., Proc. COST 257 11th Management Committee Meeting, 20-21 Jan. 2000, Barcelona, COST-257 TD(00)03) a queueing system with two traffic classes and a single reservation for the high-priority class is described (wherein the reservation is reused). The resulting delay differentiation is therefore very small, static and uncontrollable.
In the prior art no scheduling algorithm is described that allows shaping the distribution of the queueing delay perceived by each traffic class with regard to their quantiles. With the α-quantile of the delay d perceived by the packets (of a certain traffic class) is meant the value dα so that a fraction α of the packets have a delay of at least this value, i.e. Prob[d≧dα]=α. Further it is desirable to have a scheduling algorithm that allows for early provision of tight delay bounds.
Hence, there is a need for a scheduling mechanism that meets such requirements.
In the paper ‘Approximation of the Mean Waiting Time in a Finite Buffer Queue with a Combination of HOL-priority and Buffer-Reservation Schemes’ (S. Sumita, IEEE Trans. Comm., vol. E86-B, no. 11, November 2003, pp. 3283-3287) delay priority and loss priority are controlled by head-of-line priority scheduling and buffer reservation. The proposed approximation is based on the known results on a HoL-priority queue with infinite buffer and a finite buffer queue with FIFO scheduling and buffer reservation.